﻿//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
//请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
//
//输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
//输出： [[1, 6], [8, 10], [15, 18]]
//解释：区间[1, 3] 和[2, 6] 重叠, 将它们合并为[1, 6].
//
//输入：intervals = [[1, 4], [4, 5]]
//输出： [[1, 5]]
//解释：区间[1, 4] 和[4, 5] 可被视为重叠区间。
//
//提示：
//	1 <= intervals.length <= 10^4
//	intervals[i].length == 2
//	0 <= starti <= endi <= 10^4

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 1.先按照左端点排序

        sort(intervals.begin(), intervals.end());
        // 2.合并区间

        int left = intervals[0][0], right = intervals[0][1];
        vector<vector<int>> ret;
        for (int i = 1; i < intervals.size(); i++) {
            int a = intervals[i][0], b = intervals[i][1];
            if (a <= right) // 有重叠部分

            {
                // 合并-求并集

                right = max(right, b);
            }
            else // 没有重叠部分

            {
                ret.push_back({ left, right }); // 加⼊到结果中

                left = a;
                right = b;
            }
        }
        // 别忘了最后⼀个区间

        ret.push_back({ left, right });
        return ret;
    }
};